package com.datastructure.test.findmaxlength;

import java.util.ArrayList;
import java.util.HashMap;

public class FindMaxLength {

    public int findMaxLength (ArrayList<Integer> nums) {
        // write code here
        int n = nums.size();
        int[] date = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int max_i = 0;
        for (int i = 0; i < n; i++) {
            int value = nums.get(i) == 0 ? 1 : -1;
            date[i] = i == 0 ? value : date[i - 1] + value;
            if (!map.containsKey(date[i])) {
                map.put(date[i], i);
            } else {
                max_i = Math.max(max_i, i - map.get(date[i]));
            }
        }
        return max_i;
    }
}
